/* Copyright 2023 Mozilla Foundation
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

class Outliner {
  #box;

  #verticalEdges = [];

  #intervals = [];

  /**
   * Construct an outliner.
   * @param {Array<Object>} boxes - An array of axis-aligned rectangles.
   * @param {number} borderWidth - The width of the border of the boxes, it
   *   allows to make the boxes bigger (or smaller).
   * @param {number} innerMargin - The margin between the boxes and the
   *   outlines. It's important to not have a null innerMargin when we want to
   *   draw the outline else the stroked outline could be clipped because of its
   *   width.
   * @param {boolean} isLTR - true if we're in LTR mode. It's used to determine
   *   the last point of the boxes.
   */
  constructor(boxes, borderWidth = 0, innerMargin = 0, isLTR = true) {
    let minX = Infinity;
    let maxX = -Infinity;
    let minY = Infinity;
    let maxY = -Infinity;

    // We round the coordinates to slightly reduce the number of edges in the
    // final outlines.
    const NUMBER_OF_DIGITS = 4;
    const EPSILON = 10 ** -NUMBER_OF_DIGITS;

    // The coordinates of the boxes are in the page coordinate system.
    for (const { x, y, width, height } of boxes) {
      const x1 = Math.floor((x - borderWidth) / EPSILON) * EPSILON;
      const x2 = Math.ceil((x + width + borderWidth) / EPSILON) * EPSILON;
      const y1 = Math.floor((y - borderWidth) / EPSILON) * EPSILON;
      const y2 = Math.ceil((y + height + borderWidth) / EPSILON) * EPSILON;

      // 左边的竖线 和 右边的竖线
      const left = [x1, y1, y2, true];
      const right = [x2, y1, y2, false];
      this.#verticalEdges.push(left, right);

      minX = Math.min(minX, x1);
      maxX = Math.max(maxX, x2);
      minY = Math.min(minY, y1);
      maxY = Math.max(maxY, y2);
    }

    // box的宽度
    const bboxWidth = maxX - minX + 2 * innerMargin;
    // box的高度
    const bboxHeight = maxY - minY + 2 * innerMargin;
    // box的最小值的偏移量？最小还要再减小？
    const shiftedMinX = minX - innerMargin;
    const shiftedMinY = minY - innerMargin;
    const lastEdge = this.#verticalEdges.at(isLTR ? -1 : -2);

    // 最后一个点，在最后一堵墙的右下角
    const lastPoint = [lastEdge[0], lastEdge[2]];

    // Convert the coordinates of the edges into box coordinates.
    // 将墙的位置先减去最小的x和y值，再变成百分号
    for (const edge of this.#verticalEdges) {
      const [x, y1, y2] = edge;
      edge[0] = (x - shiftedMinX) / bboxWidth;
      edge[1] = (y1 - shiftedMinY) / bboxHeight;
      edge[2] = (y2 - shiftedMinY) / bboxHeight;
    }

    this.#box = {
      x: shiftedMinX,
      y: shiftedMinY,
      width: bboxWidth,
      height: bboxHeight,
      lastPoint,
    };
  }

  /**
   * 这里调用了一个算法，来绘制区域的外轮廓。
   * 首先获取box的所有左右两个边（即平行于y轴的两条边）
   * 然后将这些边从左到右进行排序
   * 如下图所示
   *                   -----
   *                y3|  B  |y4
   *      ------------|     |
   *     |             -----
   *   y1|      A        |y2
   *      ---------------
   * 有AB两个正方形，有y1 y2 y3 y4四条边
   * 这四条边分别是box A和B的两条平行于y轴的边
   * 下面开始介绍绘制这个算法绘制外边框的算法：
   * 首先将 y1 y2 y3 y4 这四条边从左到右，从上到下排序
   * 排序结果是 (y1, y3, y2, y4)
   * 然后逐个迭代，迭代的时候要注意对左侧边和右侧边的处理事不一样的
   * 先处理y1，因为y1没有什么特别的，直接保留：
   * 得到如下图形
   *      |            
   *   y1'|
   * 继续处理y3：y3因为和y1有重复的部分，因此需要去除掉重复的部分
   * 处理后结果大概如下所示：
   *                 y3'|
   *      |            
   *   y1'|
   * 紧接着处理y2，处理y2的时候不用考虑y1，但是要考虑和y3(是y3不是y3')重叠的部分
   * 之后的到如下图形：
   *                 y3'|
   *      |                
   *   y1'|                | y2'
   * 因为y2'和y3之间有交集，要把交集的部分去掉。
   * y4同理，即可获得一整个完整的外边框（竖直部分）了
   *                 y3'|      | y4'
   *      |                    |
   *   y1'|                | y2'
   */
  getOutlines() {
    // We begin to sort lexicographically the vertical edges by their abscissa,
    // and then by their ordinate.
    // 这里对每一条垂直的线做个排序
    // 因为每一条线都是垂直的，所以每条线都有一个x值，表示这条线的位置
    // 两个y值，表示这条线的在x线上的起始位置
    // 先比较x线，小的靠前，大的靠后
    // 如果x线是一样的，线段y线起点较小的靠前，较大的靠后
    // 如果y线起点也一样，比终点，终点小的靠前，大得靠后
    this.#verticalEdges.sort(
      (a, b) => a[0] - b[0] || a[1] - b[1] || a[2] - b[2]
    );

    // We're now using a sweep line algorithm to find the outlines.
    // We start with the leftmost vertical edge, and we're going to iterate
    // over all the vertical edges from left to right.
    // Each time we encounter a left edge, we're going to insert the interval
    // [y1, y2] in the set of intervals.
    // This set of intervals is used to break the vertical edges into chunks:
    // we only take the part of the vertical edge that isn't in the union of
    // the intervals.
    // 从左到右一条一条的迭代这些线，如果遇到的是一个左线，就把[y1, y2]值加入到intervals里去
    // 这些interval主要是用来将垂直边分隔危一个个块：我们只取哪些不在区间部分的垂直边。
    const outlineVerticalEdges = [];
    for (const edge of this.#verticalEdges) {
      if (edge[3]) {
        // edge[3]的值是true或者是false，如果是true，则是左边
        outlineVerticalEdges.push(...this.#breakEdge(edge));

        // insert实质上只插入了y1和y2的值
        this.#insert(edge);
      } else {
        // Right edge.
        this.#remove(edge);
        outlineVerticalEdges.push(...this.#breakEdge(edge));
      }
    }
    
    // 这最后返回的确实是外轮廓的信息
    return this.#getOutlines(outlineVerticalEdges);
  }

  #getOutlines(outlineVerticalEdges) {
    const edges = [];
    const allEdges = new Set();

    for (const edge of outlineVerticalEdges) {
      const [x, y1, y2] = edge;
      edges.push([x, y1, edge], [x, y2, edge]);
    }

    // We sort lexicographically the vertices of each edge by their ordinate and
    // by their abscissa.
    // Every pair (v_2i, v_{2i + 1}) of vertices defines a horizontal edge.
    // So for every vertical edge, we're going to add the two vertical edges
    // which are connected to it through a horizontal edge.
    edges.sort((a, b) => a[1] - b[1] || a[0] - b[0]);
    for (let i = 0, ii = edges.length; i < ii; i += 2) {
      const edge1 = edges[i][2];
      const edge2 = edges[i + 1][2];
      edge1.push(edge2);
      edge2.push(edge1);
      allEdges.add(edge1);
      allEdges.add(edge2);
    }
    const outlines = [];
    let outline;

    while (allEdges.size > 0) {
      const edge = allEdges.values().next().value;
      let [x, y1, y2, edge1, edge2] = edge;
      allEdges.delete(edge);
      let lastPointX = x;
      let lastPointY = y1;

      outline = [x, y2];
      outlines.push(outline);

      while (true) {
        let e;
        if (allEdges.has(edge1)) {
          e = edge1;
        } else if (allEdges.has(edge2)) {
          e = edge2;
        } else {
          break;
        }

        allEdges.delete(e);
        [x, y1, y2, edge1, edge2] = e;

        if (lastPointX !== x) {
          outline.push(lastPointX, lastPointY, x, lastPointY === y1 ? y1 : y2);
          lastPointX = x;
        }
        lastPointY = lastPointY === y1 ? y2 : y1;
      }
      outline.push(lastPointX, lastPointY);
    }
    return { outlines, box: this.#box };
  }

  getBox(){
    return this.#box;
  }

  #binarySearch(y) {
    const array = this.#intervals;
    let start = 0;
    let end = array.length - 1;

    while (start <= end) {
      const middle = (start + end) >> 1;
      const y1 = array[middle][0];
      if (y1 === y) {
        return middle;
      }
      if (y1 < y) {
        start = middle + 1;
      } else {
        end = middle - 1;
      }
    }
    return end + 1;
  }

  #insert([, y1, y2]) {
    // 插入的时候 按照 y1 从小到大插入
    const index = this.#binarySearch(y1);
    this.#intervals.splice(index, 0, [y1, y2]);
  }

  #remove([, y1, y2]) {
    const index = this.#binarySearch(y1);
    for (let i = index; i < this.#intervals.length; i++) {
      const [start, end] = this.#intervals[i];
      if (start !== y1) {
        break;
      }
      if (start === y1 && end === y2) {
        this.#intervals.splice(i, 1);
        return;
      }
    }
    for (let i = index - 1; i >= 0; i--) {
      const [start, end] = this.#intervals[i];
      if (start !== y1) {
        break;
      }
      if (start === y1 && end === y2) {
        this.#intervals.splice(i, 1);
        return;
      }
    }
  }

  // breakEdge 在这里主要是去掉 重复的线段部分
  // 不考虑x值的情况下，假设我的interval 是 [2,5] [3,7], [9,10]
  // 如果需要去重的线段是[2,7]，那么直接返回空，因为[2,4] [4,7]已经分别在[2,5] [3,7]这两段中有了
  // 如果需要去重的线段是[3,10]，那么应该返回 [7,9]，因为[3,7]和[9,10]都已经被包含了
  // 如果需要去重的线段是[1,12]，那么应该返回[1,2],[7,9],[10,12]，因为其余部分都已经有了
  #breakEdge(edge) {
    // 这两个let都应该是const，在调试结束后应当改回来
    const [x, y1, y2] = edge;
    const results = [[x, y1, y2]];

    // 先找到y2所在的位置，但是原因是....?
    // 因为 this.#intervals 是按照y1的大小来排序的
    // 这个index的出现，也就是说 起点比y2小的，都不看
    const index = this.#binarySearch(y2);

    for (let i = 0; i < index; i++) {
      const [start, end] = this.#intervals[i];
      // 对于每一个interval
      for (let j = 0, jj = results.length; j < jj; j++) {
        const [, y3, y4] = results[j];
        // 如果interval和edge没有任何交集，则不处理
        if (end <= y3 || y4 <= start) {
          // There is no intersection between the interval and the edge, hence
          // we keep it as is.
          continue;
        }
        // 看交集情况，如果y3在start之后，y4也在end之后，取较小的end
        // 如果y3在start之后，y4在end之前，如果result长度为1，直接返回
        // 如果result长度大于1，则删除掉这个result
        if (y3 >= start) {
          if (y4 > end) {
            // 直接把y4大于end那一部分的值 砍掉，相当于不要了
            results[j][1] = end;
          } else {
            // 如果result被某个interval直接包住的话，即 y3 >= start, y4 <= end
            // 那么这个result直接就不要了
            if (jj === 1) {
              return [];
            }
            // The edge is included in the interval, hence we remove it.
            results.splice(j, 1);
            j--;
            jj--;
          }
          continue;
        }
        // 如果y3 < start，即y3在start之前
        // result将结束的值改成start
        results[j][2] = start;
        // 如果y4在end之后，则追加一条新的线，
        if (y4 > end) {
          results.push([x, end, y4]);
        }
      }
    }
    return results;
  }
}

export { Outliner };
